// 堆是什么？
// 堆是一中特殊的完全二叉树
// 所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点

// JS中通常用数组表示堆 （广度优先遍历存入数组）
// 左侧子节点的位置是 2 * index + 1
// 右侧子节点的位置是 2 * index + 2
// 父节点的位置是 (index - 1) / 2

// 堆的应用
// 堆能高效、快速地找出最大值和最小值，时间复杂度：O(1)
// 找出第 K 个最大（小）元素

// 第 K 个最大元素
// 步骤
// 1. 构建一个最小堆，并将元素依次插入堆中
// 2. 当堆的容量超过 K，就删除堆顶
// 3. 插入结束后，堆顶就是第 K 个最大元素


// 实现：最小堆类
// 在类里，声明一个数组，用来装元素
// 主要方法： 插入、删除堆顶、获取堆顶、获取堆大小
class MinHeap {
  constructor () {
    this.heap = []
  }

  swap (i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }

  // 获取父节点位置
  getParentIndex (i) {
    // return Math.floor((i - 1) / 2) 取商
    return (i - 1) >> 1 // 效果同上
  }

  // 获取左侧子节点位置
  getLeftIndex (i) {
    return i * 2 + 1
  }

  // 获取右侧子节点位置
  getRightIndex (i) {
    return i * 2 + 2
  }

  // 上移
  shiftUp (index) {
    if (index === 0) { return }
    const parentIndex = this.getParentIndex(index)
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }

  // 下移
  shiftDown (index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)

    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }

    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }

  // 插入
  // 将值插入堆的底部，即数组的尾部
  // 然后上移：将这个值和它的父节点进行交换，知道父节点小于等于这个插入的值
  // 大小为 K 的堆中插入元素的时间复杂度为 O(log K)
  insert (value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }

  // 删除堆顶
  // 用数组尾部元素替换堆顶（直接删除堆顶会破坏堆结构）
  // 然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶
  // 大小为 K 的堆中删除堆顶的时间复杂度为 O(log K)
  pop () {
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
  }

  // 获取堆顶
  peek () {
    return this.heap[0]
  }

  // 获取堆的大小
  size () {
    return this.heap.length
  }
}

const h = new MinHeap()
h.insert(5)
console.log(h)
h.insert(2)
console.log(h)
h.insert(1)
console.log(h)
h.insert(4)
console.log(h)
h.insert(3)
console.log(h)
h.pop()
console.log(h)
